題目：103. Binary Tree Zigzag Level Order Traversal

連結：https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

• 等級：Medium

解題思路

1. 使用level紀錄階層，除２計算由左到右還右到左．

class Solution {
    private void zigzagOrder(TreeNode root,int level,List<List<Integer>> save)
    {
        if (root == null)
            return;
        if (save.size() == level)
        {
            List<Integer> li = new ArrayList<Integer>();
            li.add(root.val);
            save.add(li);
        }
        else
        {
            if (level % 2 == 0)
                save.get(level).add(root.val);
            else
                save.get(level).add(0, root.val);
        }
        zigzagOrder(root.left,level+1,save);
        zigzagOrder(root.right,level+1,save);
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> save = new ArrayList<List<Integer>>();
        zigzagOrder(root,0,save);
        return save;
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：98. Validate Binary Search Tree

連結：https://leetcode.com/problems/validate-binary-search-tree/description/

• 等級：Medium

解題思路

1. root left小於root，root right 大於root

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return false;
        }

        return isValid(root, null, null);
    }

    private boolean isValid(TreeNode root, Integer min, Integer max){
        if(root == null){
            return true;
        }

        if(min != null && root.val <= min){
            return false;
        }

        if(max != null && root.val >= max){
            return false;
        }

        return isValid(root.right, root.val, max) && isValid(root.left, min, root.val);
    }
}

• Time complexity: O(n)
• Space complexity: O(1)